namespace algo {
    db EStd(Sta &sta) { // O(n^2)
        db E = 0;
        for (Circ &x : sta) E += protDist(x);
        for (auto it1 = sta.begin(); it1 != sta.end(); ++it1)
            for (auto it2 = next(it1); it2 != sta.end(); ++it2)
                E += intrDist(*it1, *it2);
        return E;
    }
    db ESgc(Sta &sta, Sta::iterator &it1) { // O(n)
        db E = protDist(*it1);
        for (auto it2 = sta.begin(); it2 != sta.end(); ++it2)
            if (it2 != it1) E += intrDist(*it1, *it2);
        return E;
    }
    std::vector<db> ESgc(Sta &sta) { // O(n^2)
        std::vector<db> res(sta.size()); auto it3 = res.begin();
        for (Circ &x : sta) *(it3++) += protDist(x);
        it3 = res.begin();
        for (auto it1 = sta.begin(); it1 != sta.end(); ++it1, ++it3) {
            auto it4 = next(it1) - sta.begin() + res.begin();
            for (auto it2 = next(it1); it2 != sta.end(); ++it2, ++it4) {
                db d = intrDist(*it1, *it2); *it3 += d, *it4 += d;
            }
        }
        return res;
    }
    void init(Sta&);
    void SA(Sta&);
    std::tuple<bool, Sta> solve() {
        auto st = clock();
        Sta initSta, ansSta; db ansE = LDBL_MAX;
        initSta.reserve(cnt), ansSta.reserve(cnt);
        init(initSta);
        while (1.0L * (clock() - st) < timLmt * CLOCKS_PER_SEC) {
            Sta curSta = initSta; SA(curSta); db curE = EStd(curSta);
            fprintf(stderr, "SA E=%.2Lf\n", curE);
            if (curE < ansE) ansSta = curSta, ansE = curE;
        }
        fprintf(stderr, "E=%.2Lf\n", ansE);
        return std::make_tuple(ansE <= 0.00L, ansSta);
    }
}
using algo::solve;
